import collections
class Solution(object):
    def minimumTime(self, n, relations, time):
        d = collections.defaultdict(int)
        e = collections.defaultdict(set)
        for u, v in relations:
            u -= 1
            v -= 1
            e[u].add(v)
            d[v] += 1
        st = [0] * n
        now = []
        for i in range(n):
            if d[i] == 0:
                now.append(i)
                st[i] = time[i]
        while now:
            next_st = []
            for node in now:
                for v in e[node]:
                    d[v] -= 1
                    st[v] = max(st[v], st[node] + time[v])
                    if d[v] == 0:
                        next_st.append(v)
            now = next_st
        return max(st)
data = Solution()
n = 5
relations = [[1,5],[2,5],[3,5],[3,4],[4,5]]
time = [1,2,3,4,5]
print(data.minimumTime(n, relations, time))